By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 27, Issue 5, pp. 1221-1513

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Processor-Ring Communication: A Tight Asymptotic Bound on Packet Waiting Times

E. G. Coffman, Jr., Nabil Kahale, and F. T. Leighton

pp. 1221-1236

BibTeX  Abstract Full Text:  PDF

Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems

Madhav V. Marathe, Harry B. Hunt, III, Richard E. Stearns, and Venkatesh Radhakrishnan

pp. 1237-1261

BibTeX  Abstract Full Text:  PDF

Approximately Counting Hamilton Paths and Cycles in Dense Graphs

Martin Dyer, Alan Frieze, and Mark Jerrum

pp. 1262-1272

BibTeX  Abstract Full Text:  PDF

A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity

Greg Barnes, Jonathan F. Buss, Walter L. Ruzzo, and Baruch Schieber

pp. 1273-1282

BibTeX  Abstract Full Text:  PDF

Monotone Circuits for Connectivity Have Depth (log n)2-o(1)

Mikael Goldmann and Johan Håstad

pp. 1283-1294

BibTeX  Abstract Full Text:  PDF

Complexity Analysis of a Parallel Lattice Basis Reduction Algorithm

C. Heckler and L. Thiele

pp. 1295-1302

BibTeX  Abstract Full Text:  PDF

On the Fault Tolerance of Some Popular Bounded-Degree Networks

F. Thomson Leighton, Bruce M. Maggs, and Ramesh K. Sitaraman

pp. 1303-1333

BibTeX  Abstract Full Text:  PDF

On the Complexity of Negation-Limited Boolean Networks

Robert Beals, Tetsuro Nishino, and Keisuke Tanaka

pp. 1334-1347

BibTeX  Abstract Full Text:  PDF

Simple Fast Parallel Hashing by Oblivious Execution

Joseph Gil and Yossi Matias

pp. 1348-1375

BibTeX  Abstract Full Text:  PDF

A Filter Model for Concurrent $\lambda$-Calculus

Mariangiola Dezani-Ciancaglini, Ugo de'Liguoro, and Adolfo Piperno

pp. 1376-1419

BibTeX  Abstract Full Text:  PDF

Downward Separation Fails Catastrophically for Limited Nondeterminism Classes

R. Beigel and J. Goldsmith

pp. 1420-1429

BibTeX  Abstract Full Text:  PDF

The PL Hierarchy Collapses

Mitsunori Ogihara

pp. 1430-1437

BibTeX  Abstract Full Text:  PDF

Generating Low-Degree 2-Spanners

Guy Kortsarz and David Peleg

pp. 1438-1456

BibTeX  Abstract Full Text:  PDF

Performing Work Efficiently in the Presence of Faults

Cynthia Dwork, Joseph Y. Halpern, and Orli Waarts

pp. 1457-1491

BibTeX  Abstract Full Text:  PDF

Time--Space Tradeoffs For Undirected st-Connectivity on a Graph Automata

Jeff A. Edmonds

pp. 1492-1513

BibTeX  Abstract Full Text:  PDF